1. Field of the Invention
The present invention relates to packet scheduling methods and apparatus for use, for example, in wireless communication systems.
2. Description of the Related Art
FIG. 1 shows parts of a wireless communication system 1. The system includes a plurality of base stations 2, only one of which is shown in FIG. 1. The base station 2 serves a cell in which a plurality of individual users may be located. Each user has an individual user equipment (UE). Only the user equipments UE2, UE11 and UE50 are shown in FIG. 1. Each UE is, for example, a portable terminal (handset) or portable computer.
As is well known, in a code-division multiple access (CDMA) system the signals transmitted to different UEs from the base station (also known as “node B”) are distinguished by using different channelisation codes. In so-called third generation wireless communication systems a high speed downlink packet access (HSDPA) technique has been proposed for transmitting data in the downlink direction (from the base station to the UEs). In this technique a plurality of channels are available for transmitting the data. These channels have different channelisation codes. For example, there may be ten different channels C1 to C10 available for HSDPA in a given cell or sector of a cell. In HSDPA, downlink transmissions are divided up into a series of transmission time intervals (TTI), and a packet of data is transmitted on each different available channel to a selected UE. A new choice of which UE is served by which channel can be made in each TTI.
FIG. 2 shows an example of the operation of the HSDPA technique over a series of transmission time intervals TTI1 to TTI9. As shown in FIG. 2, in TTI1 it is determined that two packets will be sent to UE50, four packets will be sent to UE11 and four packets will be sent to UE2. Accordingly, two channels are allocated to UE50 and four channels each are allocated to UE11 and UE2. Thus, as shown in FIG. 1, UE50 is allocated channels C1 and C2, UE11 is allocated channels C3 to C6, and UE2 is allocated channels C7 to C10.
In the next transmission time interval TTI2 a new user equipment UE1 is sent one packet, and the remaining UEs specified in TTI1 continue to receive packets.
Thus, effectively the HSDPA system employs a number of parallel shared channels to transmit data in packet form from the base station to the different UEs. This system is expected to be used, for example, to support world wide web (WWW) browsing.
In order to decide which UE should be served on which channel in each TTI a packet scheduling technique is employed. Conventionally, two basic types of scheduling technique have been considered for use in HSDPA: a round-robin (RR) scheduling technique and a maximum carrier-to-interference ratio (max C/I) technique.
The basic round-robin technique first compiles a list of the UEs which currently have data waiting at the transmitter (base station) for transmission. For each TTI the last UE in the list will have the highest priority for the next TTI. Accordingly, the UEs are serviced in a round robin fashion. In the simplest round-robin scheduling technique, it is assumed that the UE with the highest priority takes all of the channels. However, a packet-weighted round-robin technique is also known. This allocates the available channels to a group of users in each TTI based on the relative amounts of data for the different UEs. In this packet-weighted technique UEs which have more data waiting for transmission are allocated more channels.
The round-robin scheduling techniques emphasise fairness amongst the competing UEs in terms of radio resource allocation. However, they tend to provide relatively poor total throughput of data.
The max C/I scheduling technique is similar to the round-robin scheduling technique except that the list of UEs having waiting data is sorted in each TTI based on a carrier-to-interference ratio (C/I) reported by each UE. The C/I is a measure of the quality of the channel. By sorting the list of UEs based on C/I, UEs which have a better channel quality are given a higher chance to be selected. In the simplest version of the technique, all of the channels are allocated to the UE with waiting data that has the highest C/I. A packet-weighted variant is also possible, in which instead of selecting a single UE having the highest C/I, a group of UEs with the highest C/I values is selected, and the available channels are divided up amongst the group of UEs based on the relative amounts of data which those UEs have waiting for transmission.
The max C/I scheduling technique tends to maximise the total throughput of data but this is at the expense of fairness. It can be seen that UEs which report poor C/I values, for example because they are far from the base station or because there are many other interfering UEs in the vicinity, will only very rarely be selected. Thus, these UEs are likely to suffer from unacceptably long delays in receiving packets.
Another scheduling technique is disclosed in “A proposal of all-IP mobile wireless network architecture—QoS packet scheduler for base stations”, Masahiro Ono et al, NEC Corporation, Technical Report of IEICE, MoMuC2002-3 (2002-05), pp. 13-18. This packet scheduling technique aims to meet quality of service (QoS) requirements of different UEs and to maximise the system capacity by adaptively allocating time-slots according to the wireless link quality and the required QoS levels. The technique employs a hierarchy of different individual schedulers including a max C/I scheduler, a proportional fairness (PF) scheduler, a weighted round robin (WRR) scheduler and a priority round robin (PRR) scheduler. Packets to be scheduled are pre-classified by a classifier according to the different QoS requirements of the different UEs. Packets belonging to different classes are then applied to different schedulers in the first level of schedulers in the hierarchy. Further scheduling is carried out in second and third levels of the hierarchy. In this way, multiple individual schedulers are used to cater for the different requirements of different classes of services. However, partitioning the scheduling process in a fixed way or slow-changing dynamic way proves difficult and inefficient because of the fast-changing dynamics of the radio channels. The result may be that the scheduler assigned to one partition (class of service) will be under a high pressure to provide the required QoS level, but the scheduler assigned to another partition (class of service) is underutilised and has spare capacity. It is also found that the efficiency and performance of such partitioned schedulers degrade considerably as the amount of the shared bandwidth and the range of services having differing requirements increase. Attempts to recover some of the lost efficiency in such partitioned schedulers in practice result only in increased computational complexity and attendant costs.
In United Kingdom patent application no. 0303859.3, from which the present application claims priority and which has been published in the official file of the present PCT application (publication no. WO 2004/075568), the present inventor has proposed a packet scheduling method for scheduling packets of data for transmission from a transmitter via at least one channel to a plurality of receivers, for example in an HSDPA system of a wireless communications network. Weightings are assigned to at least two different aspects of scheduling performance, for example quality of service, delay and fairness. For each individual receiver at least one combined measure of the scheduling performance in the different aspects is produced according to the assigned weightings. The respective combined measures for different receivers are employed to decide the receiver(s) to which packets are to be transmitted. PCT application no. PCT/GB2004/000649, filed on the same date as the present application and published as WO 2004/075569, corresponds to GB 0303859.3. The entire contents of GB 0303859.3 and the PCT application are incorporated herein by reference, and copies of these applications have been filed with the present application.
This packet scheduling method enables scheduling of data to be carried out for all the receivers as a single group, without having to classify the receivers into different scheduling classes such as different service types. The method also enables the scheduling to take account of several different performance aspects without significant computational complexity.
In this method, the weights are assigned values taking account of the expected traffic scenario. For example, various simulations were carried out, each relating to a simulated traffic environment in which there are 40 UEs in total. 10 of these UEs were assumed to be attempting to receive real-time video and the remaining 30 UEs were assumed to be attempting WWW browsing sessions. In one simulation, the total aggregate traffic load was assumed to be approximately constant over a series of 5,000 TTIs (ten second period). In another simulation, the WWW users were assumed to become active in a staggered manner, giving rise to a variable input load on the scheduler. In a third simulation, it was assumed that a slowing mechanism was provided by the HSDPA system for WWW browsing. Such a slowing mechanism prevents the downloading of a new session unless a previous session has been successfully downloaded completely.
It was found from these simulations that the weightings which must be applied to the different aspects of scheduling performance need to be significantly different for the different traffic scenarios. In view of this, it was envisaged that the weightings could be adjustable by an operator of the scheduler so that when the expected traffic scenario changes the weights can be changed as well. It was also envisaged in United Kingdom patent application no. 0303859.3 that the weights could be adjusted automatically during operation of the apparatus.
In S. Abedi, S. Vadgama, “Hybrid Genetic Packet Scheduling and radio Resource Management for High Speed Downlink Packet Access”, WPMC 2002 Conference, Hawaii, pp. 1192-1196 the present inventor has also proposed a packet scheduling technique employing a genetic algorithm. In this technique, a plurality of candidate scheduling solutions are generated for each TTI. Each candidate solution corresponds to an individual in the genetic algorithm and specifies which receivers are to be allocated which channels in the TTI concerned. The fitness of each candidate scheduling solution is determined. The fitness may take into account several different measures of performance of the scheduling solution concerned, for example throughput, delay and fairness. The individual performance measures may be weighted when determining the fitness for each candidate solution. Individuals in the current generation are selected as parents based on the fitness values of the corresponding candidate solutions. Fitter solutions have a higher chance of being selected as parents. Children (candidate solutions for the next generation) are produced by the selected parents in accordance with genetic operators such as crossover and mutation. In this way, over a series of iterations (generations) the genetic algorithm refines the candidate scheduling solutions until, at some point, a single best solution is selected for the TTI under consideration.
Such a genetic algorithm offers the potential for achieving much better scheduling performance than conventional techniques such as round robin scheduling and max C/I scheduling.
Another packet scheduling method has been proposed by the present inventor in S. Abedi, S. Vadgama, “A Radio Aware Random Iterative Scheduling Technique for High Speed Downlink Packet Access”, VTC 2002, Fall, vol. 4, pp. 2322-2326, 24-28, September 2002. This method also generates a plurality of candidate scheduling solutions for each TTI. At least one of the candidate solutions is generated randomly. The fitness of each candidate solution may be determined in the same way as for the proposed scheduling method based on a genetic algorithm, as described above.
The success of such packet scheduling methods is also heavily dependent on the choice of appropriate weights for weighting the individual performance measures when determining the fitness for each candidate solution. In particular, different weights are required to deal with different traffic scenarios.
The same problem of assigning proper weights under different conditions also arises in other types of packet schedulers conceived for use in wireless networks. For example, a so-called proportionally fair (PF) scheduler is described in R. Agrawal, et. al. “Class and Channel Condition Based Scheduler for EDGE/GPRS”, Proc. of SPIE, vol.#4531, August 2001, and A. Jalali, R. Padovani, R. Pankaj; “Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system”, VTC 2000, Spring, vol. 3, pp. 1854-1858, May 2000. The PF scheduler also requires the assignment of proper weights under different traffic load and channel conditions.
The dynamic mobile cellular environment makes the setting of appropriate weights a challenging task. Firstly, there may be enormous variation between channel conditions.
FIG. 3(A) is a graph illustrating schematically how the reported C/I values for four different UEs vary over a series of N TTIs under first channel conditions. In this case, the C/I values are relatively stable but there is a consistent difference in C/I values from one UE to the next. Some UEs have relatively poor channel conditions over the entire series of N TTIs, and others have relatively good channel conditions over the entire series. Under these channel conditions, many of the scheduling methods outlined above will tend to have difficulty in achieving fairness as between the different UEs. Other aspects of the scheduling performance, such as overall throughput, are not likely to be a problem.
FIG. 3(B) illustrates the variation of C/I values for four different UEs under second channel conditions different from the first channel conditions the subject of FIG. 3(A). In this case, the variation in C/I values of each individual UE is much greater than in FIG. 3(A) and at different times over the series of N TTIs the different UEs each have good channel conditions. In this situation, it is not a challenge to achieve fairness. Instead, it may be difficult to achieve a high overall throughput or some other desired aspect of scheduling performance.
As well as dealing with variable channel conditions of the kind described with reference to FIGS. 3(A) and 3(B), an effective packet scheduling method must also cope with input traffic load dynamics (variable input pipes) and UEs whose profiles change rapidly as they move and change to using difference services. In particular, a UE may move rapidly from one cell to another. In this case, the packet data which has already been buffered in the existing Node B must be transferred to the new Node B. If there are many such transfers, there may be frequent step-function-like changes in the total load to be handled by a packet scheduler at a given Node B. In some cases, as described later in the present specification, this load variation has been found empirically to lead to a so-called “run-away” phenomenon and instability of the packet scheduler when the weights are fixed. The empirical studies described later have also shown that radical input pipe variations may lead to a significant drop in performance for one or more of the desired aspects of scheduling performance.
The drop in performance may affect only one class of service, for example, real-time services, whilst not affecting another class of service such as non-conversational services. Some schedulers, such as the PF scheduler, purport to address this problem by partitioning the scheduling according to the type of service, and assigning different fixed weights to the different partitions. However, in practice this may prove inefficient since the numbers of UEs using each type of service may change, with the result that the fixed weights are unable to provide a good QoS for the service concerned. For example, if the weights assigned to the different services are fixed and the number of high-bit-rate non-real-time users downloading WWW sessions increases significantly, the Node B would be under huge pressure to provide an acceptable QoS for the real-time video conversational sessions.
It is therefore desirable to provide a packet scheduling method which enables the weights applied to different measures of scheduling performance to be adjusted automatically so as to enable the scheduler to work efficiently under a variety of different traffic scenarios.